package leetcode100

// TODO 中心扩散法 【-】 最长回文子串
// TODO https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}

	start, end := 0, 0

	for i := 0; i < len(s); i++ {
		left1, right1 := expandAroundCenter(s, i, i)   // 单中心元素
		left2, right2 := expandAroundCenter(s, i, i+1) // 双中心元素
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	return s[start : end+1]
}

// 以一个点为中心, 向外延伸
func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s); left, right = left-1, right+1 {
		if s[left] != s[right] {
			break;
		}
	}
	return left + 1, right - 1
}
